package algorithms;

/**
 * 分治
 * 规模更小子问题
 * 递归
 * 合并
 */
public class 最大子数组 {

    public static void main(String[] args) {
        int[] arr = new int[]{13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
        int[] maxSubArray = findMaxSubArray(arr, 0, arr.length - 1);
        System.out.println(maxSubArray[0]);
        System.out.println(maxSubArray[1]);
        System.out.println(maxSubArray[2]);
    }

    private static int[] findMaxSubArray(int[] arr, int low, int high) {
        if (low == high) {
            return new int[]{low, high, arr[low]};
        }

        int mid = (low + high) / 2;

        int[] left = findMaxSubArray(arr, low, mid);
        int[] right = findMaxSubArray(arr, mid + 1, high);
        int[] cross = findMaxCrossingSubArray(arr, low, mid, high);

        if (left[2] >= right[2] && left[2] >= cross[2]) {
            return left;
        } else if (right[2] >= left[2] && right[2] >= cross[2]) {
            return right;
        } else {
            return cross;
        }
    }

    private static int[] findMaxCrossingSubArray(int[] arr, int low, int mid, int high) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        int leftIndex = mid;
        for (int i = mid; i >= low; i--) {
            sum += arr[i];
            if (sum >= leftSum) {
                leftIndex = i;
                leftSum = sum;
            }
        }

        int rightSum = Integer.MIN_VALUE;
        int sum2 = 0;
        int rightIndex = mid + 1;
        for (int i = mid + 1; i <= high; i++) {
            sum2 += arr[i];
            if (sum2 > rightSum) {
                rightIndex = i;
                rightSum = sum2;
            }
        }

        return new int[]{leftIndex, rightIndex, leftSum + rightSum};
    }
}
